package _interview150;

import java.util.*;

/**
 * 30. 串联所有单词的子串
 */
public class No30 {
    private Map<String, Integer> origin;
    private Map<String, Integer> curMap;

    public List<Integer> findSubstring(String s, String[] words) {
        int n = s.length(), m = words.length, wordLen = words[0].length();
        // 统计 words 中「每个目标单词」的出现次数
        origin = new HashMap<>();
        for (String str : words) origin.put(str, origin.getOrDefault(str, 0) + 1);
        List<Integer> ans = new ArrayList<>();
        for (int start = 0; start < wordLen; start++) {
            // 构建一个当前子串对应的哈希表，统计当前子串中「每个目标单词」的出现次数
            curMap = new HashMap<>();
            // 滑动窗口的大小固定是 m * wordLen，每次将下一个单词添加进 curMap，上一个单词移出 curMap
            for (int end = start; end + wordLen <= n; end += wordLen) {
                String cur = s.substring(end, end + wordLen);
                curMap.put(cur, curMap.getOrDefault(cur, 0) + 1);
                if (end - start >= m * wordLen) {
                    String prev = s.substring(end - m * wordLen, end - (m - 1) * wordLen);
                    curMap.put(prev, curMap.get(prev) - 1);
                }
                if (isValid()) ans.add(end - (m - 1) * wordLen);
            }
        }
        return ans;
    }

    private boolean isValid() {
        return origin.entrySet().stream().allMatch(entry -> curMap.containsKey(entry.getKey()) && curMap.get(entry.getKey()) >= entry.getValue());
    }
}
